package algorithm.leetcode;

import algorithm.templates.TreeNode;

public class NO543_二叉树的直径 {
    static class Solution {

        int answer = 0;

        public int diameterOfBinaryTree(TreeNode root) {
            depth(root);
            return answer;
        }

        private int depth(TreeNode root) {
            if (root == null) return 0;

            int left = depth(root.left);
            int right = depth(root.right);

            answer = Math.max(answer, left + right);

            return Math.max(left, right) + 1;
        }
    }

    static class SelfSolution {

        int answer = 0;

        public int diameterOfBinaryTree(TreeNode root) {
            findMaxDepth(root);
            return answer;
        }

        private int findMaxDepth(TreeNode root) {
            if (root == null) {
                return 0;
            } else {

                int left = findMaxDepth(root.left);
                int right = findMaxDepth(root.right);

                answer = Math.max(answer, left + right);
                return Math.max(left, right) + 1;
            }
        }
    }
}
